{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "164cd9fc",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "#  32\\.  常用聚类算法对比评估  # \n",
    "\n",
    "##  32.1.  介绍  # \n",
    "\n",
    "前面讲解了近十种不同思路的聚类算法，最后一个挑战的目的是探索不同算法在不同形状数据集上的聚类效果和所需时间。 \n",
    "\n",
    "##  32.2.  知识点  # \n",
    "\n",
    "  * 算法对数据形状的适应性 \n",
    "\n",
    "  * 相同条件下的算法效率 \n",
    "\n",
    "##  32.3.  生成测试数据  # \n",
    "\n",
    "挑战前，需要先生成测试数据，我们使用 ` make_moons()  ` ， ` make_circles()  ` ， ` make_blobs()  ` 生成 3 组数据。 \n",
    "\n",
    "Exercise 32.1 \n",
    "\n",
    "挑战：使用 sklearn 生成 3 组测试数据，并绘制出散点图（横排拼接子图）。 \n",
    "\n",
    "规定： \n",
    "\n",
    "  * 为了方便后续实验，你需要对 3 组测试数据进行 Min-Max 归一化处理，使得横纵坐标都在 0-1 的范围之内。 \n",
    "\n",
    "  * 3 种方法对应的参数如下： \n",
    "\n",
    "  * 三组数据均包含 100 个样本，且将随机数种子均设为 10。 \n",
    "\n",
    "  * moons 和 circles 数据添加 0.1 的噪声。 \n",
    "\n",
    "  * circles 数据内外圈间距比例因子设为 0.3。 \n",
    "\n",
    "  * blobs 数据拥有 2 个簇，且簇标准差设为 1.5。 \n",
    "\n",
    "  * 其余参数取默认值。 \n",
    "\n",
    "Min-Max 标准化同样是常用手段，其效果类似于区间缩放，可以将数值缩放到 0-1 之间。其公式为： \n",
    "\n",
    "$$\\hat x=\\frac{x-x_{min}}{x_{max}-x_{min}}$$ \n",
    "\n",
    "其中，  $x_{max}$  为样本数据的最大值，  $x_{min}$  为样本数据的最小值，  $x_{max}-x_{min}$  为极差。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76218040",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn import datasets\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "## 代码开始 ### (≈ 7-10 行代码)\n",
    "\n",
    "## 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "448896d5",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "参考答案  Exercise 32.1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c8b6ec1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn import datasets\n",
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "### 代码开始 ### ((≈ 7-10 行代码))\n",
    "moons, _ = datasets.make_moons(n_samples=100, noise=.1, random_state=10)\n",
    "circles, _ = datasets.make_circles(n_samples=100, noise=.1, factor=.3, random_state=10)\n",
    "blobs, _ = datasets.make_blobs(n_samples=100, n_features=2, centers=2, cluster_std=1.5, random_state=10)\n",
    "\n",
    "# Min-Max 归一化\n",
    "moons = (moons - np.min(moons)) / (np.max(moons) - np.min(moons))\n",
    "circles = (circles - np.min(circles)) / (np.max(circles) - np.min(circles))\n",
    "blobs = (blobs - np.min(blobs)) / (np.max(blobs) - np.min(blobs))\n",
    "\n",
    "fig, axes = plt.subplots(nrows=1, ncols=3, figsize=(16, 4))\n",
    "axes[0].scatter(moons[:, 0], moons[:, 1])\n",
    "axes[1].scatter(circles[:, 0], circles[:, 1])\n",
    "axes[2].scatter(blobs[:, 0], blobs[:, 1])\n",
    "### 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d12f940",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "期望输出 \n",
    "\n",
    "![image](https://cdn.aibydoing.com/aibydoing/images/document-uid214893labid6102timestamp1531815154644.png)\n",
    "\n",
    "##  32.4.  聚类结果对比  # \n",
    "\n",
    "接下来，拟选用 sklearn 提供的几种常用的聚类方法在上面 3 个数据集上测试聚类效果，这些聚类方法有： \n",
    "\n",
    "  * ` cluster.KMeans()  `\n",
    "\n",
    "  * ` cluster.MiniBatchKMeans()  `\n",
    "\n",
    "  * ` cluster.AffinityPropagation()  `\n",
    "\n",
    "  * ` cluster.MeanShift()  `\n",
    "\n",
    "  * ` cluster.SpectralClustering()  `\n",
    "\n",
    "  * ` cluster.AgglomerativeClustering()  `\n",
    "\n",
    "  * ` cluster.Birch()  `\n",
    "\n",
    "  * ` cluster.DBSCAN()  `\n",
    "\n",
    "Exercise 32.2 \n",
    "\n",
    "挑战：采用上述 8 个聚类方法分别在 moons, circles 和 blobs 上进行测试，并将聚类结果绘制成图。 \n",
    "\n",
    "规定：本次挑战不规定参数，请根据前面学习的内容使得聚类效果尽量更好。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29aedda1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import cluster\n",
    "\n",
    "## 代码开始 ### (> 10 行代码)\n",
    "\n",
    "## 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "627c43fc",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "参考答案  Exercise 32.2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ebca2e64",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import cluster\n",
    "\n",
    "### 代码开始 ### (> 10 行代码)\n",
    "cluster_names = ['KMeans', 'MiniBatchKMeans', 'AffinityPropagation', \n",
    "                 'MeanShift', 'SpectralClustering', 'AgglomerativeClustering', 'Birch', 'DBSCAN']\n",
    "\n",
    "cluster_estimators = [\n",
    "    cluster.KMeans(n_clusters=2),\n",
    "    cluster.MiniBatchKMeans(n_clusters=2),\n",
    "    cluster.AffinityPropagation(),\n",
    "    cluster.MeanShift(),\n",
    "    cluster.SpectralClustering(n_clusters=2, metric='nearest_neighbors', n_neighbors=6),\n",
    "    cluster.AgglomerativeClustering(n_clusters=2),\n",
    "    cluster.Birch(n_clusters=2, threshold=.1),\n",
    "    cluster.DBSCAN(eps=.1, min_samples=6, metric='euclidean')\n",
    "]\n",
    "\n",
    "for algorithm_name, algorithm in zip(cluster_names, cluster_estimators):\n",
    "\n",
    "    moons_clusters = algorithm.fit_predict(moons)\n",
    "    circles_clusters = algorithm.fit_predict(circles)\n",
    "    blobs_clusters = algorithm.fit_predict(blobs)\n",
    "\n",
    "    fig, axes = plt.subplots(nrows=1, ncols=3, figsize=(16, 4))\n",
    "    axes[0].scatter(moons[:, 0],moons[:, 1], c=moons_clusters)\n",
    "    axes[1].scatter(circles[:, 0],circles[:, 1], c=circles_clusters)\n",
    "    axes[2].scatter(blobs[:, 0],blobs[:, 1], c=blobs_clusters)\n",
    "    axes[0].set_ylabel('{}'.format(algorithm_name))\n",
    "### 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28c5a8f0",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "期望输出 \n",
    "\n",
    "![image](https://cdn.aibydoing.com/aibydoing/images/document-uid214893labid6102timestamp1531815155045.png)\n",
    "\n",
    "上图中，我们一般只能得出同一种方法在不同数据集上聚类效果好坏的结论。由于不同方法之间的聚类效果取决于具体的参数，所以并不能准确得到谁好谁坏的结果，只能作为参考。 \n",
    "\n",
    "接下来，我们想测试不同方法在不同数量级的数据集上执行速度的快慢对比。这一次，我们仅使用 ` make_blobs()  ` 生成团状测试数据。生成测试数据的函数如下： "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f48c3e9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_data(n):\n",
    "    \"\"\"\n",
    "    参数:\n",
    "    n -- 生成样本数量\n",
    "    返回:\n",
    "    blobs_data -- 样本数组\n",
    "    \"\"\"\n",
    "    blobs_data, _ = datasets.make_blobs(\n",
    "        n_samples=n, n_features=2, centers=2, cluster_std=1.5, random_state=10\n",
    "    )\n",
    "    return blobs_data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe545e16",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "Exercise 32.3 \n",
    "\n",
    "挑战：使用 ` create_data(n)  ` 生成不同规模的测试数据，并计算不同算法的聚类时间，且绘制对应的折线图。 \n",
    "\n",
    "规定： \n",
    "\n",
    "  * 生成数据规模依次为：100, 200, 300, ···, 900, 1000 等 10 组。 \n",
    "\n",
    "  * 除指定 ` n_clusters=2  ` 之外，其余参数均使用相关方法的默认参数。 \n",
    "\n",
    "提示：可以通过 time 模块记录算法运行时间，例如： "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2efb1106",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "t0 = time.time()\n",
    "cluster_estimator.fit()\n",
    "t1 = time.time()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40b4a763",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "则 ` t1-t0  ` 即为 ` cluster_estimator.fit()  ` 所花费时间。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fb0906c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "## 代码开始 ### (> 10 行代码)\n",
    "\n",
    "## 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3513d298",
   "metadata": {
    "lines_to_next_cell": 0
   },
   "source": [
    "参考答案  Exercise 32.3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fb8970a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "### 代码开始 ### (> 10 行代码)\n",
    "cluster_names = ['KMeans', 'MiniBatchKMeans', 'AffinityPropagation', \n",
    "                 'MeanShift', 'SpectralClustering', 'AgglomerativeClustering', 'Birch', 'DBSCAN']\n",
    "\n",
    "cluster_estimators = [\n",
    "    cluster.KMeans(n_clusters=2),\n",
    "    cluster.MiniBatchKMeans(n_clusters=2),\n",
    "    cluster.AffinityPropagation(),\n",
    "    cluster.MeanShift(),\n",
    "    cluster.SpectralClustering(n_clusters=2),\n",
    "    cluster.AgglomerativeClustering(n_clusters=2),\n",
    "    cluster.Birch(n_clusters=2),\n",
    "    cluster.DBSCAN()\n",
    "]\n",
    "\n",
    "cluster_t_list = []\n",
    "for algorithm_name, algorithm in zip(cluster_names, cluster_estimators):\n",
    "    t_list = []\n",
    "    for num in [i for i in range(100, 1100, 100)]:\n",
    "        data = create_data(num) # 生成数据\n",
    "        t0 = time.time()\n",
    "        moons_clusters = algorithm.fit(data)\n",
    "        t1 = time.time()\n",
    "        t_list.append(t1 - t0) # 计算聚类时间\n",
    "    print(\"{} fitted & average time:{:4f}\".format(algorithm_name, np.mean(t_list)))\n",
    "    cluster_t_list.append(t_list)\n",
    "\n",
    "plt.figure(figsize=(12, 6))\n",
    "for cluster_t, cluster_name in zip(cluster_t_list, cluster_names):\n",
    "    plt.plot(cluster_t, marker='.', label=cluster_name)\n",
    "    plt.legend()\n",
    "### 代码结束 ###"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1165dfe9",
   "metadata": {},
   "source": [
    "期望输出 \n",
    "\n",
    "![image](https://cdn.aibydoing.com/aibydoing/images/document-uid214893labid6102timestamp1531806692002.png)\n",
    "\n",
    "可以发现，Affinity Propagation，Mean Shift 以及 Spectral Clustering 花费时间上升速度较快，也是比较耗时的聚类算法。 "
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "cell_metadata_filter": "-all",
   "main_language": "python",
   "notebook_metadata_filter": "-all"
  },
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
